package leetcode.sort;

import java.awt.print.Pageable;
import java.util.Arrays;

/**
 * @author ：zsy
 * @date ：Created 2021/7/13 22:16
 * @description：插入排序
 */
public class InsertSort {
    public static void main(String[] args) {
        InsertSort(new int[]{101, 34, 119, 1});
    }

    /**
     * 原始数组： 101 34 119 1
     * 第一次插入： 34 101 119 1
     * 第二次插入： 34 101 119 1
     * 第三次插入： 1 34 101 119
     */
    public static void InsertSort(int[] arr) {
        int len = arr.length;
        for (int i = 1; i < len; i++) {
            int insertIndex = i - 1;
            int insertValue = arr[i];
            while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            if (insertIndex + 1 != i) {
                arr[insertIndex + 1] = insertValue;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
